class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ans = 0;
        int sum = 0;
        bool flag = false;

        for (int i = 0; i < n; ++i) {
            if (sum < 0) {
                sum = A[i];
            } else {
                sum += A[i];
            }
            if (!flag || ans < sum) {
                ans = sum;
                flag = true;
            }
        }
        return ans;
    }
};
